package com.jiang.专题.动态规划.Q124;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/11 23:22
 */
class Solution {
    int res = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return res;
    }

    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // 递归计算左右子节点的最大值
        // 只有在最大值大于 0 时，才会选取对应子节点
        int l = Math.max(0, dfs(node.left));
        int r = Math.max(0, dfs(node.right));

        // 如果当前节点在路径上，产生了一条新路径, 新路径由当前节点 + 左节点最大路径 + 右节点最大路径组成
        int newPath = l + r + node.val;
        res = Math.max(res, newPath);

        // 因为一个节点只能用一次，所以返回的是当前节点的值加上左右节点的最大值，给node的父亲节点使用
        return node.val + Math.max(l, r);
    }
}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}